小A想要合成一个化合物。初始时，容器里有 a 克的物质A。小A每次操作都会向容器中加入 b 克物质A与 c 克物质B，当容器中物质A与物质B的比值不大于 d 时，说明小A合成成功了.

前 3 个测试点满足

1≤a,b,c,d≤105

后 2 个测试点满足

1≤a,b,c,d≤109

输入格式：

输入 4 个整数a, b, c, d.

输出格式：

若可以合成化合物，那么输出小A的最小操作次数，否则输出−1

输入样例1：

1
5 2 3 2

输出样例1：

进行 1 次操作后，容器里有 7 克物质A与3 克物质B, 此时 7/3>2, 不满足条件，2次操作后，容器里有 9 克物质A与6 克物质B, 此时 9/6<=2 满足条件，因此答案为 2.

1
2

输入样例2：

1
6 9 2 3

输出样例2：

1
-1

输入样例3：

1
100000 99999 100000 1

输出样例3：

1
100000

思路

直接暴力循环求解会超时，得不到满分

设x为某时物质A的质量，y为某时物质B的质量，操作n次后满足条件，即满足(a+b*n)/c*n <= d，根据该公式推导出n的解公式即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    double a, b, c, d;
    cin >> a >> b >> c >> d;
    double ret = -a / (b - c * d); //推导出的解公式
    if(ret > 0) {
        if(ret == (long)ret) {
            cout << (long)ret << endl;
        } else {
            cout << (long)ret + 1 << endl;
        }
    } else {
        cout << "-1" << endl;
    }
    return 0;
}